package linked;
import java.util.*;

import org.junit.Test;

public class Ex234 {
    class Solution1 {
        public boolean isPalindrome1(ListNode head) {
            if (head == null) return true;

            List<Integer> list = new ArrayList<>();
            while (head != null) {
                list.add(head.val);
                head = head.next;
            }

            int size = list.size();
            for (int i = 0; i < list.size() / 2; i++) {
                if (list.get(i) != list.get(size - i - 1)) return false;
            }
            return true;
        }

        //利用快慢指针将链表变成两半，后一半逆序；按照顺序对前后一半进行比对
        //要注意的是：根据奇偶的情况决定从什么地方开始翻转【与fast是否为空有关】
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) return true;
            ListNode fast = head.next.next, slow = head.next;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            } 
            
            ListNode start = slow;
            //这样做之后，后一半的长度总会小于等于前一半，因此之后的比较回文使用后半段是否为空做条件
            if (fast != null) start = slow.next;

            ListNode pre = start, cur = start.next;
            while (cur != null) {
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                start.next = temp;
                cur = temp;
            }

            while (pre != null) {
                if (head.val != pre.val) return false;
                pre = pre.next;
                head = head.next;
            }
            return true;
        }
    }


@Test 
public void test() {
    ListNode head = new ListNode(1), cur = head;
    cur.next = new ListNode(2);
    cur = cur.next;
    cur.next = new ListNode(2);
    cur = cur.next;
    cur.next = new ListNode(1);
    cur = cur.next;

    Solution s = new Solution();
    boolean res = s.isPalindrome(head);
    System.out.println(res);
}

class Solution {
    public boolean isPalindrome(ListNode head) {

        if (head == null || head.next == null) return true;
        ListNode fast = head, slow = head, temp = null; //temp记录中点的前一个位置，用于修改会去

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            temp = slow;
            slow = slow.next;
        }

        //将pre变成工作位置头结点，cur变成工作指针
        ListNode cur = slow, pre = slow;
        //fast为null，证明节点为偶数个，且slow在中点靠右的位置
        if (fast == null) {
            pre = new ListNode(0);
            pre.next = cur;
        } else {
            //fast.next == null, 节点为奇数个，slow在中点位置，需要换位的是右边的节点
            pre = slow;
            cur = slow.next;
        }

        pre.next = null;
        //反转从cur链表尾部的部分
        ListNode t, node = cur.next, h = cur;
        while (node != null) {
            t = node.next;
            node.next = cur;
            h.next = t;
            cur = node;
            node = t;
        } //此后，cur为链表头部[原尾部]，h为链表尾部【原头部】
        node = head;
        t = cur;
        boolean res = true;
        while (cur != null) {
            if (node.val != cur.val) res =  false;
            node = node.next;
            cur = cur.next;
        } //已经得到结果，将链表返还

        cur = t;
        node = cur.next;
        ListNode n = cur;
        while (node != null) {
            t = node.next;
            node.next = cur;
            n.next = t;
            cur = node;
            node = t;
        }
        n.next = null;
        temp.next = cur;
        System.out.println(head);
        return res;
    }
}

}